package ycj.learn.dsa.leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class ThreeSum {
    public static void main(String[] args) {
        System.out.println(new ThreeSum().threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> result = new LinkedList<List<Integer>>();

        /*空数组直接走*/
        if (nums.length == 0) return result;
        if (nums[0] > 0) return result;

        for (int i = 0; i < nums.length - 2; i++) {
            int first = nums[i];

            /*跳过重复的*/
            if (i > 0 && first == nums[i - 1]) continue;

            /*指定左右指针*/
            int l = i + 1;
            int r = nums.length - 1;

            while (l < r) {
                int second = nums[l];
                int third = nums[r];
                int sum = first + second + third;

                if (sum > 0) r--;
                else if (sum < 0) l++;
                else {
                    result.add(Arrays.asList(first, second, third));

                    /*把相等的数字跳过去*/
                    while (l < r && third == nums[--r]) ;
                    while (l < r && second == nums[++l]) ;
                }
            }
        }
        return result;
    }
}
